package _2022.hot100._279_完全平方数;

import java.util.ArrayList;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-05-22 09:23
 */
public class Solution {

    // 动态规划
    public  int numSquares2(int n){
        int[] dp=new int[n+1];
        for(int i=1;i<=n;i++){
            int minn=Integer.MAX_VALUE;
            for(int j=1;j*j<=i;j++){
                minn=Math.min(minn, dp[i-j*j]);
            }
            dp[i]=1+minn;
        }
        return dp[n];
    }

    // 超时
    public int numSquares(int n){
        int len = (int)Math.sqrt(n);
        int[] candidates=new int[len];
        int ans=Integer.MAX_VALUE;
        for(int i=0;i<len;i++){
            candidates[i]=(i+1)*(i+1);
        }
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(candidates,0,n,path, res);
        for(List<Integer> tmp:res){
            ans=Math.min(ans, tmp.size());
        }
        return ans;
    }


    private void dfs(int[] candidates, int begin, int target, List<Integer> path, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
        }
        for (int i = begin; i < candidates.length; i++) {
            path.add(candidates[i]);
            dfs(candidates, i, target-candidates[i], path, res);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        s.numSquares2(13);
    }

}
